import java.util.*;




class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}





public class project {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(i==size-1){
                        list.add(tmp.val);
                    }
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
            }
        }
        return list;
    }











    public List<Integer> rightSideView1(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(i==size-1){
                        list.add(tmp.val);
                    }
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
            }
        }
        return list;
    }













    public int sumNumbers(TreeNode root) {
        if(root==null){
            return 0;
        }
        return dfs8(root,0);
    }
    public int dfs8(TreeNode root,int tmp){
        if(root==null ){
            return 0;
        }
        int sum=tmp*10+root.val;
        if(root.left==null&&root.right==null){
            return sum;
        }else{
            return dfs8(root.left,sum)+dfs8(root.right,sum);
        }
    }














    public int sumNumbers1(TreeNode root) {
        return dfs7(root,0);
    }
    public int dfs7(TreeNode root,int sum){
        if(root==null){
            return 0;
        }
        int res=sum*10+root.val;
        if(root.left==null&&root.right==null){
            return res;
        }else{
            return dfs7(root.left,res)+dfs7(root.right,res);
        }
    }











    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new LinkedList<>();
        int len=candidates.length;
        if(len==0){
            return list;
        }
        Deque<Integer> deque=new ArrayDeque<>();
        dfs6(candidates,target,0,len,deque,list);
        return list;
    }
    public void dfs6(int[] arr,int key,int start,int end,Deque<Integer> deque,List<List<Integer>> list){
        if(key<0){
            return;
        }
        if(key==0){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=start;i<end;i++){
            deque.addLast(arr[i]);
            dfs6(arr,key-arr[i],i,end,deque,list);
            deque.removeLast();
        }
    }














    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>> list=new LinkedList<>();
        int len=candidates.length;
        if(len==0){
            return list;
        }
        Deque<Integer> deque=new ArrayDeque<>();
        dfs5(candidates,target,0,len,deque,list);
        return list;
    }
    public void dfs5(int[] arr,int key,int start,int end,Deque<Integer> deque,List<List<Integer>> list){
        if(key<0){
            return;
        }
        if(key==0){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=start;i<end;i++){
            deque.addLast(arr[i]);
            dfs5(arr,key-arr[i],i,end,deque,list);
            deque.removeLast();
        }
    }












    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list=new LinkedList<>();
        if(n<k){
            return list;
        }
        Deque<Integer> deque=new ArrayDeque<>();
        dfs4(1,n,k,deque,list);
        return list;
    }
    public void dfs4(int start,int end,int key,Deque<Integer> deque,List<List<Integer>> list){
        if(deque.size()==key){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=start;i<=end;i++){
            deque.addLast(i);
            dfs4(i+1,end,key,deque,list);
            deque.removeLast();
        }
    }














    public List<List<Integer>> combine1(int n, int k) {
        List<List<Integer>> list=new LinkedList<>();
        if(n<k){
            return list;
        }
        Deque<Integer> deque=new ArrayDeque<>();
        dfs3(1,n,k,list,deque);
        return list;
    }
    public void dfs3(int start,int end,int k,List<List<Integer>> list,Deque<Integer> deque){
        if(deque.size()==k){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=start;i<=end;i++){
            deque.addLast(i);
            dfs3(i+1,end,k,list,deque);
            deque.removeLast();
        }
    }

















    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        List<List<Integer>> list=new LinkedList<>();
        if(len==0){
            return list;
        }
        boolean[] bools=new boolean[len];
        Deque<Integer> deque=new ArrayDeque<>();
        dfs2(nums,len,0,deque,bools,list);
        return list;
    }
    public void dfs2(int[] nums,int len,int size,Deque<Integer> deque,boolean[] bools,List<List<Integer>> list){
        if(size==len){
            list.add(new LinkedList<>(deque));
            return;
        }
        for(int i=0;i<len;i++){
            if(bools[i]){
                continue;
            }
            bools[i]=true;
            deque.addLast(nums[i]);
            dfs2(nums,len,size+1,deque,bools,list);
            bools[i]=false;
            deque.removeLast();
        }
    }










    public List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> list=new LinkedList<>();
        int len=nums.length;
        if(len==0){
            return list;
        }
        boolean[] bools=new boolean[len];
        Deque<Integer> deque=new ArrayDeque<>();
        dfs1(nums,len,0,bools,deque,list);
        return list;
    }
    public void dfs1(int[] nums,int len,int size,boolean[] bools,Deque<Integer> deque,List<List<Integer>> list){
        if(len==size){
            list.add(new LinkedList<>(deque));
            return ;
        }
        for(int i=0;i<len;i++){
            if(bools[i]){
                continue;
            }
            bools[i]=true;
            deque.addLast(nums[i]);
            dfs1(nums,len,size+1,bools,deque,list);
            bools[i]=false;
            deque.removeLast();
        }
    }
}
